package org.example.leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 17. 电话号码的字母组合
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 */
public class Code17 {
    List<String> res = new ArrayList<String>();
    StringBuilder str = new StringBuilder();
    char[][] list;

    public List<String> letterCombinations(String digits) {
        // 处理空字符串情况
        if (digits == null || digits.isEmpty()) {
            return res;
        }

        // 初始化结果集（重要：每次调用方法时需要清空之前的结果）
        res.clear();
        str.setLength(0);

        list = new char[11][4];
        list[2][0] = 'a';
        list[2][1] = 'b';
        list[2][2] = 'c';
        list[3][0] = 'd';
        list[3][1] = 'e';
        list[3][2] = 'f';
        list[4][0] = 'g';
        list[4][1] = 'h';
        list[4][2] = 'i';
        list[5][0] = 'j';
        list[5][1] = 'k';
        list[5][2] = 'l';
        list[6][0] = 'm';
        list[6][1] = 'n';
        list[6][2] = 'o';
        list[7][0] = 'p';
        list[7][1] = 'q';
        list[7][2] = 'r';
        list[7][3] = 's';
        list[8][0] = 't';
        list[8][1] = 'u';
        list[8][2] = 'v';
        list[9][0] = 'w';
        list[9][1] = 'x';
        list[9][2] = 'y';
        list[9][3] = 'z';
        backtrack(digits, 0);
        return res;
    }

    private void backtrack(String digits, int index) {
        if (index == digits.length()) {
            res.add(str.toString());
            return;
        }
        //当前是哪个数字
        int digit = digits.charAt(index) - '0';
        char[] letter = list[digit];
        for (int i = 0; i < letter.length; i++) {
            if (letter[i] != '\0') {
                str.append(letter[i]);
                backtrack(digits, index + 1);
                str.deleteCharAt(str.length() - 1);
            }
        }
    }
}
